By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 28, Issue 5, pp. 1541-1922

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs

Weiping Shi and Douglas B. West

pp. 1541-1551

BibTeX  Abstract Full Text:  PDF

Product Range Spaces, Sensitive Sampling, and Derandomization

Hervé Brönnimann, Bernard Chazelle, and Jiri Matousek

pp. 1552-1575

BibTeX  Abstract Full Text:  PDF

Automatic Nonzero Structure Analysis

Aart J. C. Bik and Harry A. G. Wijshoff

pp. 1576-1587

BibTeX  Abstract Full Text:  PDF

Stack and Queue Layouts of Directed Acyclic Graphs: Part II

Lenwood S. Heath and Sriram V. Pemmaraju

pp. 1588-1626

BibTeX  Abstract Full Text:  PDF

Membership in Constant Time and Almost-Minimum Space

Andrej Brodnik and J. Ian Munro

pp. 1627-1640

BibTeX  Abstract Full Text:  PDF

Derandomizing Approximation Algorithms Based on Semidefinite Programming

Sanjeev Mahajan and H. Ramesh

pp. 1641-1663

BibTeX  Abstract Full Text:  PDF

The Dynamic Parallel Complexity of Computational Circuits

Gary L. Miller and Shang-Hua Teng

pp. 1664-1688

BibTeX  Abstract Full Text:  PDF

The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms

Ueli M. Maurer and Stefan Wolf

pp. 1689-1721

BibTeX  Abstract Full Text:  PDF

Selecting the Median

Dorit Dor and Uri Zwick

pp. 1722-1758

BibTeX  Abstract Full Text:  PDF

Structure in Approximation Classes

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, and linebreak Luca Trevisan

pp. 1759-1782

BibTeX  Abstract Full Text:  PDF

An Efficient Data Structure for Lattice Operations

Maurizio Talamo and Paola Vocca

pp. 1783-1805

BibTeX  Abstract Full Text:  PDF

Bandwidth Allocation with Preemption

Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, and Baruch Schieber

pp. 1806-1828

BibTeX  Abstract Full Text:  PDF

An Optical Simulation of Shared Memory

Leslie Ann Goldberg, Yossi Matias, and Satish Rao

pp. 1829-1847

BibTeX  Abstract Full Text:  PDF

Time-Lapse Snapshots

Cynthia Dwork, Maurice Herlihy, Serge Plotkin, and Orli Waarts

pp. 1848-1874

BibTeX  Abstract Full Text:  PDF

The Construction of Huffman Codes is a Submodular ("Convex") Optimization Problem Over a Lattice of Binary Trees

D. Stott Parker and Prasad Ram

pp. 1875-1905

BibTeX  Abstract Full Text:  PDF

Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

Haim Kaplan, Ron Shamir, and Robert E. Tarjan

pp. 1906-1922

BibTeX  Abstract Full Text:  PDF